1654C - Alice and the Cake - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
// typedef
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<long, long> pll;
typedef vector<pii> vpii;
typedef deque<int> di;
typedef deque<ll> dll;
// define instruction
#define double long double
#define rep(i, x, y) for (int i = x; i < y; i++)
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define all(x) begin(x), end(x)
// define constants
#define MOD 1000000007
#define inf 1e18
#define PI 3.141592653589793238462
// defined functions
ll setBitNumber(ll n)
{
	if (n == 0)
		return 0;
	ll msb = 0;
	n = n / 2;
	while (n != 0)
	{
		n = n / 2;
		msb++;
	}
	return (1 << msb);
}
ll countBits(ll number)
{ // log function in base  take only integer part
	return (ll)log2(number) + 1;
}
ll mul(ll a, ll b, ll mod = 1000000007)
{
	return ((a % mod) * (b % mod)) % mod;
}
ll gcd(ll a, ll b)
{
	if (b == 0)
	{
		return a;
	}
	return gcd(b, a % b);
}
bool isPrime(ll n)
{
	if (n <= 1)
		return false;
	if (n == 2 || n == 3)
		return true;
	if (n % 2 == 0 || n % 3 == 0)
		return false;

	for (ll i = 5; i <= sqrt(n); i = i + 6)
		if (n % i == 0 || n % (i + 2) == 0)
			return false;
	return true;
}
ll expo(ll a, ll b, ll mod)
{
	ll res = 1;
	while (b > 0)
	{
		if (b & 1)
			res = (res * a) % mod;
		a = (a * a) % mod;
		b = b >> 1;
	}
	return res;
}
int countDigit(ll n)
{
	return floor(log10(n) + 1);
}
ll lcm(ll a, ll b)
{
	return (a / gcd(a, b)) * b;
}
ll countDivisors(ll n)
{
	ll cnt = 0;
	for (ll i = 1; i <= sqrt(n); i++)
	{
		if (n % i == 0 && isPrime(i))
		{
			if (n / i == i)
				cnt++;
			else // Otherwise count both
				cnt = cnt + 2;
		}
	}
	return cnt;
}
// main solution
//@aniketrajput25
void solve()
{
 ll n;
        cin >> n;
        vector<ll> a(n);
        ll sum = 0;
        map<ll, ll> m;
        for (ll i = 0; i < n; i++)
        {
            cin >> a[i];
            sum += a[i];
            m[a[i]]++;
        }
        if (n == 1)
        {
            cout << "YES" << "\n";
        }
        else
        {
            queue<ll> q;
            q.push(sum);
            vector<ll> ans;
            ll cnt=0;
            while (!q.empty() && ans.size() < n-1 && cnt<=n-1)
            {
                cnt++;
                ll s = q.front();
                q.pop();
                ll a1 = floor((double)s / 2);
                ll a2 = ceil((double)s / 2);
 
                if (m[a1] > 0)
                {
                    m[a1]--;
                    ans.push_back(a1);
                }
                else
                {
                    q.push(a1);
                }
 
                if (m[a2] > 0)
                {
                    m[a2]--;
                    ans.push_back(a2);
                }
                else
                {
                    q.push(a2);
                }
            }
 
            if (ans.size() != n)
            {
                cout << "NO" << "\n";
            }
            else
            {
                sort(ans.begin(), ans.end());
                sort(a.begin(), a.end());
                bool ok = true;
                for (ll i = 0; i < n; i++)
                {
                    if (a[i] != ans[i])
                    {
                        ok = false;
                        cout << "NO" << "\n";
                        break;
                    }
                }
                if (ok)
                {
                    cout << "YES" <<"\n";
                }
            }
        }
}
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}